Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem

Iterated greedy search is a simple and effective metaheuristic for combinatorial problems. Its flexibility enables the incorporation of components from other metaheuristics with the aim of obtaining effective and powerful hybrid approaches. We propose a tabu-enhanced destruction mechanism for iterated greedy search that records the last removed objects and avoids removing them again in subsequent iterations. The aim is to provide a more diversified and successful search process with regards to the standard destruction mechanism, which selects the solution components for removal completely at random.     

A global best artificial bee colony algorithm for global optimization

The artificial bee colony (ABC) algorithm is a relatively new optimization technique which has been shown to be competitive to other population-based algorithms. However, there is still an insufficiency in the ABC algorithm regarding its solution search equation, which is good at exploration but poor at exploitation. Inspired by differential evolution (DE), we propose a modified ABC algorithm (denoted as ABC/best), which is based on that each bee searches only around the best solution of the previous iteration in order to improve the exploitation. In addition, to enhance the global convergence, when producing the initial population and scout bees, both chaotic systems and opposition-based learning method are employed. Experiments are conducted on a set of 26 benchmark functions. The results demonstrate good performance of ABC/best in solving complex numerical optimization problems when compared with two ABC based algorithms.     

Joint detection and tracking of size-varying infrared targets based on block-wise sparse decomposition

The high variability of target size makes small target detection in Infrared Search and Track (IRST) a challenging task. A joint detection and tracking method based on block-wise sparse decomposition is proposed to address this problem. For detection, the infrared image is divided into overlapped blocks, and each block is weighted on the local image complexity and target existence probabilities. Target-background decomposition is solved by block-wise inexact augmented Lagrange multipliers. For tracking, label multi-Bernoulli (LMB) tracker tracks multiple targets taking the result of single-frame detection as input, and provides corresponding target existence probabilities for detection. Unlike fixed-size methods, the proposed method can accommodate size-varying targets, due to no special assumption for the size and shape of small targets. Because of exact decomposition, classical target measurements are extended and additional direction information is provided to improve tracking performance. The experimental results show that the proposed method can effectively suppress background clutters, detect and track size-varying targets in infrared images.     

Time series interpolation via global optimization of moments fitting

Most time series forecasting methods assume the series has no missing values. When missing values exist, interpolation methods, while filling in the blanks, may substantially modify the statistical pattern of the data, since critical features such as moments and autocorrelations are not necessarily preserved.     

Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods

The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper, we present two tabu search implementations, one involving an exhaustive search of the 2-opt neighborhood and the other involving an exhaustive search of the insertion neighborhood. We also present techniques to significantly speed up the search of the two neighborhoods. Our computational experiments show that the speed up techniques are effective, and our tabu search implementations are competitive. Our tabu search implementations improved previously known best solutions for 23 out of the 43 large sized SRFLP benchmark instances.     

Iterated tabu search for the circular open dimension problem

This paper investigates the circular open dimension problem (CODP), which consists of packing a set of circles of known radii into a strip of fixed width and unlimited length without overlapping. The objective is to minimize the length of the strip. In this paper, CODP is solved by a series of sub-problems, each corresponding to a fixed strip length. For each sub-problem, an iterated tabu search approach, named ITS, is proposed. ITS starts from a randomly generated solution and attempts to gain improvements by a tabu search procedure. After that, if the obtained solution is not feasible, a perturbation operator is subsequently employed to reconstruct the incumbent solution and an acceptance criterion is implemented to determine whether or not accept the perturbed solution. As a supplementary method, the length of the strip is determined in monotonously decreasing way, with the aid of some post-processing techniques. The search terminates and returns the best found solution after the allowed computation time has been elapsed. Computational experiments based on numerous well-known benchmark instances show that ITS produces quite competitive results, with respect to the best known results, while the computational time remains reasonable for each instance.     

Optimal keyword bidding in search-based advertising with target exposure levels

Search-based advertising has become very popular since it provides advertisers the ability to attract potential customers with measurable returns. In this type of advertising, advertisers bid on keywords to have an impact on their ad’s placement, which in turn affects the response from potential customers. An advertiser must choose the right keywords and then bid correctly for each keyword in order to maximize the expected revenue or attain a certain level of exposure while keeping the daily costs in mind. In response to increasing need for analytical models that provide a guidance to advertisers, we construct and examine deterministic optimization models that minimize total expected advertising costs while satisfying a desired level of exposure. We investigate the relationship between our problem and the well-known continuous non-linear knapsack problem, and then solve the problem optimally by utilizing Karush–Kuhn–Tucker conditions. We present practical managerial insights based on the analysis of both a real-life data from a retailer and a hypothetical data.